package 算法.NiuKe.JZ;

import 算法.NiuKe.ListNode;

import java.util.HashSet;

/**
 * @author:谢君臣
 * @Date:2021/4/2616:41
 * @version:1.0
 * @function:   在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
 * 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
 */
public class JZ57 {
    public ListNode deleteDuplication(ListNode pHead) {
        HashSet<Integer> set = new HashSet<>();
        HashSet<Integer> re = new HashSet<>();
        ListNode p = pHead;
        while (p!=null){
            ListNode node = p;
            if (set.contains(node.val))re.add(node.val);
            else set.add(node.val);
            p = p.next;
        }
        while (pHead!=null&&re.contains(pHead.val))pHead = pHead.next;
        if (pHead==null)
            return pHead;
        p = pHead;
        while (p.next!=null){
            if (re.contains(p.next.val))
                p.next = p.next.next;
            else p = p.next;
        }
        return pHead;
    }
}
